package 二叉树;

public class JZ33二叉搜索树的后序遍历序列 {

    /**
     * 输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历结果。
     * 如果是则返回 true，否则返回 false。假设输入的数组的任意两个数字都互不相同。
     *
     * 参考以下这颗二叉搜索树：
     *      5
     *     / \
     *    2   6
     *   / \
     *  1   3
     * 示例 1：
     * 输入: [1,6,3,2,5]
     * 输出: false
     * 示例 2：
     * 输入: [1,3,2,6,5]
     * 输出: true
     *
     * 提示：
     * 数组长度 <= 1000
     */

    //方法一: 递归  最右边为根节点  然后从左向右遍历,第一个比根节点大的就是右孩子节点
    //       然后就可以按照这个规则计数,判断是否可以。
    //方法二: 倒序遍历,利用栈,略
    public boolean verifyPostorder(int[] postorder) {
        if(postorder==null||postorder.length<1){
            return false;
        }
        return method1(postorder);
    }

    private boolean method1(int[] postorder) {
        return dfs(postorder,0,postorder.length-1);
    }

    private boolean dfs(int[] postorder,int left,int right) {

        if(right<=left){
            return true;
        }

        //最右根根节点 中间的为右孩子节点
        int index=left;

        while (postorder[index]<postorder[right]){
            //将左子树遍历完毕
            index++;
        }

        int leftIndex=index-1;

        while (postorder[index]>postorder[right]){
            //将右子树遍历完毕
            index++;
        }
        if((index-left)!=(right-left)){
            return false;
        }

        return dfs(postorder,left,leftIndex)&&dfs(postorder,leftIndex+1,right-1);
    }

    private boolean method2() {
        return false;
    }

    public static void main(String[] args) {
        JZ33二叉搜索树的后序遍历序列 jz=new JZ33二叉搜索树的后序遍历序列();
        int[] arr={4, 8, 6, 12, 16, 14, 10};
        boolean result = jz.method1(arr);
        System.out.println(result);
    }

}
